package org.example.tree;


public class BinarySortTree {

    private Node root;

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    public  void add(Node node){
        if (root == null){
            root = node;
        }else{
            root.add(node);
        }
    }


    public void infixOrder(){
        if (root != null){
            root.infixOrder();
        }else{
            System.out.println("空");
        }
    }

    public Node search(int value){
        if (root != null){
            return root.search(value);
        }else{
            System.out.println("二叉树为空");
            return null;
        }
    }

    public Node searchParent(int value){
        if (root != null){
            return root.searchParent(value);
        }else{
            System.out.println("空");
            return null;
        }
    }

    /**
     *
     * @param target 传入的节点（）当作目标节点的右子树根节点
     * @return 返回的以node为根节点的二叉排序树的最小节点的值
     */
    public int delRightTreeMin(Node target){

        //查找目标右子树的节点
        while(target.left != null){
            target = target.left;
        }
        //将其删除
        delNode(target.value);
        //将其值传回
        return target.value;
    }

    public void delNode(int value){

        if(root == null){
            return;
        }else{
            Node targetNode = search(value);
            //System.out.println("要删除的目标节点" + targetNode);
            if (targetNode == null){
                return;
            }
            if (root.left == null && root.right == null){
                root = null;
                return;
            }
            Node parent = searchParent(value);
            //System.out.println("要删除的目标节点的父节点" + parent);
            //删除叶子节点
            if(targetNode.left == null && targetNode.right == null){
                if (parent.left != null && value == parent.left.value){
                    parent.left = null;
                }else if (parent.right!=null && value == parent.right.value){
                    parent.right = null;
                }
                //删除带有左右节点的父节点
                /*
                * 思路：先找出要删除的目标节点的右子树的最小节点，然后将其的值保存再删除
                * 最后就将目标节点的值改为其右子树最小节点的值
                * */
            }else if(targetNode.left != null && targetNode.right != null){
                targetNode.value = delRightTreeMin(targetNode.right);
            }else{
                //删除带有左节点的节点
                if (targetNode.left != null){
                    if (parent != null) {
                        if (parent.left.value == value) {
                            parent.left = targetNode.left;
                        } else {
                            parent.right = targetNode.left;
                        }
                    }else{
                        root = targetNode.left;
                    }
                }else{
                    if (parent != null) {
                        //删除带有右节点的节点
                        if (parent.left.value == value) {
                            parent.left = targetNode.right;
                        } else {
                            parent.right = targetNode.right;
                        }
                    }else{
                        root = targetNode.right;
                    }
                }
            }
        }

    }

}

